// 归并排序，acm练习风格
// 测试链接 : https://www.luogu.com.cn/problem/P1177
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成"Main"，可以直接通过
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

public class Code01_MergeSort {

    // 定义数组最大长度，这里假设最大为100001
    public static int MAXN = 100001;
    // 用于存储待排序的数组
    public static int[] arr = new int[MAXN];
    // 辅助数组，用于归并过程
    public static int[] help = new int[MAXN];
    // 数组元素个数
    public static int n;

    public static void main(String[] args) throws IOException {
        // 使用BufferedReader读取输入流，提高读取效率
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 使用StreamTokenizer来解析输入流中的数据
        StreamTokenizer in = new StreamTokenizer(br);
        // 使用PrintWriter来输出结果，同样是为了提高效率
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

        // 获取输入的数组元素个数
        in.nextToken();
        n = (int) in.nval;

        // 读取数组元素
        for (int i = 0; i < n; i++) {
            in.nextToken();
            arr[i] = (int) in.nval;
        }

        // 如果使用递归版的归并排序，可以调用这个方法（这里被注释掉了）
        // mergeSort1(0, n - 1);
        // 使用非递归版的归并排序
        mergeSort2();

        // 输出排序后的数组，除了最后一个元素每个元素后面跟一个空格
        for (int i = 0; i < n - 1; i++) {
            out.print(arr[i] + " ");
        }
        // 单独输出最后一个元素并换行
        out.println(arr[n - 1]);

        // 刷新输出缓冲区，确保所有数据都被输出
        out.flush();
        // 关闭输出流
        out.close();
        // 关闭输入流
        br.close();
    }

    // 归并排序递归版
    // 假设l...r一共n个数
    // 时间复杂度分析：
    // T(n) = 2 * T(n/2) + O(n)，这里a = 2（子问题个数），b = 2（每次子问题规模缩小为原来的1/2），c = 1
    // 根据master公式，时间复杂度为O(n * logn)
    // 空间复杂度为O(n)，因为递归调用栈的深度最多为n层
    public static void mergeSort1(int l, int r) {
        // 如果左边界等于右边界，说明只有一个元素，已经有序，直接返回
        if (l == r) {
            return;
        }
        // 计算中间位置
        int m = (l + r) / 2;
        // 对左半部分进行递归排序
        mergeSort1(l, m);
        // 对右半部分进行递归排序
        mergeSort1(m + 1, r);
        // 合并左右两部分
        merge(l, m, r);
    }

    // 归并排序非递归版
    // 时间复杂度为O(n * logn)
    // 空间复杂度为O(n)
    public static void mergeSort2() {
        // 一共发生O(logn)次分组
        for (int l, m, r, step = 1; step < n; step <<= 1) {
            // 内部分组merge，时间复杂度O(n)
            l = 0;
            while (l < n) {
                // 计算当前分组的中间位置
                m = l + step - 1;
                // 如果右半部分的起始位置超出了数组范围，说明这一组不需要合并，直接处理下一组
                if (m + 1 >= n) {
                    break;
                }
                // 计算当前分组的右边界，防止超出数组范围
                r = Math.min(l + (step << 1) - 1, n - 1);
                // 合并当前分组
                merge(l, m, r);
                // 更新下一组的左边界
                l = r + 1;
            }
        }
    }

    // l....r 一共有n个数
    // 这个方法用于合并两个有序子数组，时间复杂度为O(n)
    public static void merge(int l, int m, int r) {
        // 辅助数组的索引
        int i = l;
        // 左子数组的起始索引
        int a = l;
        // 右子数组的起始索引
        int b = m + 1;

        // 比较两个子数组的元素，将较小的元素放入辅助数组
        while (a <= m && b <= r) {
            help[i++] = arr[a] <= arr[b]? arr[a++] : arr[b++];
        }

        // 左侧指针、右侧指针，必有一个越界、另一个不越界
        // 如果左子数组还有剩余元素，将它们放入辅助数组
        while (a <= m) {
            help[i++] = arr[a++];
        }
        // 如果右子数组还有剩余元素，将它们放入辅助数组
        while (b <= r) {
            help[i++] = arr[b++];
        }

        // 将辅助数组中的元素复制回原数组
        for (i = l; i <= r; i++) {
            arr[i] = help[i];
        }
    }
}